1. Field of the Invention
The present invention relates to content addressable memory (CAM) arrays. More specifically, the present invention relates to CAM arrays having a longest prefix match capability.
2. Discussion of Related Art
Conventional Internet protocol (IP) addresses include Class A, Class B and Class C addresses, each having a length of 32-bits. FIG. 1 is a block diagram illustrating Class A IP address 101, Class B IP address 102 and Class C IP address 103.
Class A addresses, such as Class A address 101, are identified by a logic “0” bit at bit location [0] (i.e., the most significant bit location). The next seven bits of Class A address 101 (i.e., bits [1:7]), along with the first bit (i.e., bit [0]), define a network address, and the last 24 bits of Class A address 101 (i.e., bits [8:31]) define a host address within the network. The set of Class A addresses are therefore capable of defining 128 networks, each having 224 hosts.
Similarly, Class B addresses, such as Class B address 102, are identified by logic “10” bits at bit locations [0:1] (i.e., the two most significant bit locations). The next 14 bits of Class B address 102 (i.e., bits [2:15]), along with the first two bits (i.e., bits [0:1]), define a network address, and the last 16 bits of Class B address 102 (i.e., bits [16:31]) define a host address. The set of Class B addresses are therefore capable of defining 214 networks, each having 216 hosts.
Finally, Class C addresses, such as Class C address 103, are identified by logic “110” bits at bit locations [0:2] (i.e., the three most significant bit locations). The next 21 bits of Class C address (i.e., bits [3:23]), along with the first three bits (i.e., bits [0:2]), define a network address, and the last 8 bits of Class C address (i.e., bits [24:3]) define a host address. The set of Class C addresses are therefore capable of defining 221 221 networks, each having 256 hosts.
Growth of the Internet has resulted in a shortage of Class A, Class B and Class C IP addresses. This shortage of IP addresses, in turn, has resulted in routing difficulties. In response, Classless Inter-Domain Routing (CIDR) has been developed to help relieve these routing difficulties. CIDR allows for the flexible allocation of network and host addresses within a 32-bit IP address. For example, CIDR allows the network address, which is hereinafter referred to as a “prefix”, to be defined by the first N bits of the 32-bit IP address, where N is an integer less than 32. The host address is then defined by the last M bits of the 32-bit IP address, wherein M is equal to 32 minus N. The most common values of N are in the range of 13 to 27, inclusive. CIDR advantageously expands the number of IP addresses available within a 32-bit field, and allows for improved allocation of IP addresses.
CIDR addresses are processed using a “longest prefix match” algorithm, which is typically implemented using a content addressable memory (CAM) array.
FIG. 2 is a block diagram of a conventional router 20 used to process CIDR addresses. As described below, router 20 implements a longest prefix match algorithm. Router 20 includes input port 201, CAM array 202, priority encoder 230, SRAM array 240, output switch 250 and output ports 261–264. CAM array 202 is logically divided into CAM sub-arrays 208–228. Each of CAM sub-arrays 208–228 is dedicated to store prefixes of a predetermined length. For example, CAM sub-array 228 is configured to store 28-bit prefixes, CAM sub-array 225 is configured to store 25-bit prefixes, and CAM sub-array 208 is configured to store 8-bit prefixes. Within CAM array 202, longer prefixes are assigned a higher priority than shorter prefixes. CAM sub-arrays 208–228 are arranged in order of priority, from highest-priority CAM sub-array 228, which stores 28-bit prefixes, to lowest-priority CAM sub-array 208, which stores 8-bit prefixes. Within each of CAM sub-arrays 208–228, the prefixes are arranged in order from highest priority to lowest priority. Thus, the first entry of CAM sub-array 228 stores the highest priority 28-bit prefix and the last entry of CAM sub-array 228 will store the lowest priority 28-bit prefix.
An input packet (PACKETIN) that includes a 32-bit CIDR address (CIDR[31:0]) is applied to input port 201. In response, input port 201 provides the CIDR[31:0] address to CAM array 202. In response, CAM sub-arrays 208–228 will assert match signals for each prefix that matches the corresponding bits of the applied address CIDR[31:0]. These match signals are provided to priority encoder 230. In response, priority encoder 230 provides an INDEX signal representative of the asserted match signal having the highest priority. The INDEX signal is used as an address to access a corresponding entry of SRAM array 240. The entry retrieved from SRAM 240 includes an output port number, which is provided to output switch 250. In response, output switch 250 routes selected portions of the input packet to one of the output ports 661–664 as an output packet (PACKETOUT). Although only four output ports 261–264 are illustrated, it is understood that router 20 typically includes many more output ports.
CAM array 202, which has a finite capacity, is initially allocated to implement CAM sub-arrays 208–228 having fixed, predetermined sizes. For example, each of CAM sub-arrays 208–228 may be allocated to include 4 k (4096) entries. This allocation is intended to provide extra capacity in each CAM sub-array to allow for the addition of new prefixes. For example, each of CAM sub-arrays 213–227 may initially be programmed to store about 3 k prefixes. In this example, each of CAM sub-arrays 208–228 includes an unused capacity of about 1 k entries, which is allocated to allow for the addition of new prefixes in the future. However, by allocating each of CAM sub-arrays 208–228 in this manner, one quarter of the available capacity (and layout area) of CAM array 202 is initially unused.
Moreover, the unused capacity of CAM sub-arrays 208–228 may be improperly allocated in view of the actual prefixes subsequently added to CAM array 202. For example, a relatively large number (i.e., >1 k) of additional 27-bit prefixes may need to be added to CAM sub-array 227, while zero additional 8-bit CIDR prefixes may need to be added to CAM sub-array 208. In this case, CAM sub-array 227 would have insufficient capacity, while CAM sub-array 213 would have extra capacity. As a result, CAM array 202 would have to be completely re-allocated. Such re-allocation is time consuming and inefficient.
In addition, SRAM array 240 is initially allocated in the same manner as CAM array 202. As a result, SRAM array 240 must be re-allocated whenever CAM array 202 is re-allocated. Again, such re-allocation is time consuming and inefficient.
It would therefore be desirable to have an improved router look-up table for more efficiently implementing longest prefix match comparisons.